package com.leetcode;

/**
 * 两数相加
 * 两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 将两个数相加，并以相同形式返回一个表示和的链表。
 * 除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * @author winson
 * @create 2022-03-25 15:21
 */
public class TwoNumbersAddingSolution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        /**
         * 相加需要考虑是否需要进位：通过除10得到进位，通过求模得到余数，为当前值
         * 同时需要考虑什么是否停止相加：只有当两个链表都遍历完了，此时停止，只要有任何一个不为空说明没有遍历完
         * 停止后，需要考虑进位是否大于0，如果大于0需要补位
         */
        ListNode listNode = new ListNode();
        ListNode currentNode = listNode;
        int carry = 0; // 进位，默认0
        int sum = 0; // 两数与进位相加之和
        while (l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            sum = v1 + v2 + carry;
            carry = sum / 10;
            int val = sum % 10;
            ListNode node = new ListNode(val);
            currentNode.next = node;
            currentNode = node;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if (carry > 0) {
            ListNode listNode1 = new ListNode(carry);
            currentNode.next = listNode1;
        }
        return listNode.next;
    }

    public static void main(String[] args) {
        ListNode listNode13 = new ListNode(4);
        ListNode listNode12 = new ListNode(3, listNode13);
        ListNode listNode1 = new ListNode(2, listNode12);

        ListNode listNode23 = new ListNode(5);
        ListNode listNode22 = new ListNode(3, listNode23);
        ListNode listNode2 = new ListNode(4, listNode22);
        TwoNumbersAddingSolution solution = new TwoNumbersAddingSolution();
        ListNode listNode = solution.addTwoNumbers(listNode1, listNode2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
